using System;
using System.Collections.Generic;
namespace GraphSpace
{
	public class Dial:IPQ
	{
		private List<int>[] buckets;
		private Dictionary<int, Dial_Knoten> elements;
		private int c;
		
		public Dial (int C)
		{
			this.c = C;								
			buckets = new List<int>[c+2];		
			for(int i=0; i<c+2; i++)
				buckets[i] = new List<int>();
			elements = new Dictionary<int, Dial_Knoten>();
		}
			
		public Knoten extractHead()
		{
			// ersten nicht leeren Bucket suchen und erstes Element zurückgeben
			for(int i=0; i< c+2; i++)
			{	
				if(buckets[i].Count>0)
				{
					return elements[buckets[i][0]];
				}
		    }
		
			return null;
		}
		
		// versucht den Knoten in einen Dial_knoten zu casten
		public bool insert(Knoten item)
		{
			try
			{
				return insert((Dial_Knoten)item);
			}
			catch
			{
				Console.WriteLine("Fehler im Dial : es wurde ein Knoten anstatt eines Dial_Knoten übergben!");
				return false;
			}
		}
		
		public bool insert(Dial_Knoten item)
		{	
			try
			{
				// Element in Hilfstrukturen und Bucket für unendlich eintragen
				elements.Add(item.Id, item);				// Dictionary Id -> Dial_Knoten
				buckets[c+1].Add(item.Id);				// im Unendlich-Bucket an letzter Stelle einfügen
				item.Bucket = c+1;							// Zeiger auf Bucket setzen
				item.Position = buckets[c+1].Count-1;		// Zeiger auf Position im Bucket setzen
				return true;
			}
			catch(Exception e)
			{
				Console.WriteLine("Fehler in Dial::insert : "+e.ToString());
				return false;
			}
		}
		
		public bool decreaseKey(int id, int key)
		{
			try
			{
				// Zuerst im alten Bucket entfernen und Zeiger der übrigen Elemente im Bucket aktuallisieren
				buckets[elements[id].Bucket].RemoveAt(elements[id].Position);
				for(int i = (elements[id].Position); i < buckets[elements[id].Bucket].Count; i++)
				{
					elements[buckets[elements[id].Bucket][i]].Position--;	
				}
				// Anschliessend den Knoten im neunen Bucket einfügen und seine Zeiger anpassen
				int d = key%(c+1);
				buckets[d].Add(id);
				elements[id].Bucket = d;
				elements[id].Position = buckets[d].Count-1;
				
				return true;
			}
			catch(Exception e)
			{
				Console.WriteLine("Fehler in Dial::decreaseKey("+id+", "+key+")"+e.ToString());
				return false;
			}
		}
		
		public void show()
		{
			// Alle normalen Buckets
			for(int i = 0; i< c+1; i++)
			{
				Console.WriteLine("\t"+i+". Bucket");
				foreach(int j in buckets[i])
					Console.WriteLine("\t\t"+elements[j].ToString());
			}
			// unendlicher Bucket
			Console.WriteLine("\tunendliches Bucket");
			foreach(int j in buckets[c+1])
				Console.WriteLine("\t\t"+elements[j].ToString());
		}
	}
}

